Design is a major activity of practicing engineers that requires creation of complex structures to satisfy user-defined technical requirements. Because the design process typically entails tradeoffs between competing technical considerations, the result is usually a satisfactory and compliant design as opposed to a perfect design. The design process is usually viewed as requiring creativity and human intelligence.
Design requirements in the real world often include important non-technical considerations. For example, creation of a design that does not possess the key characteristics of any previously known solution to the problem at hand results in a design that is novel. Novelty may be desired by a company for several reasons. Novelty may enable a company to obtain patent protection for its product, may enable a company to design around an existing patent to avoid infringement (of, say, a competitor's patent), or may enable a company to differentiate its product in the marketplace on the basis of the product's unique technology. Regardless of the motivation, avoidance of preexisting technology within a given field, whether patented or not, may often be important in the real-world design process. As part of the design process, a new design may be compared to the preexisting technology through a laborious process of analysis and visual inspection to insure that the new design does not posses the key characteristics of the preexisting technology.
Search Techniques
Complex structures, such as electronic circuits, automatic controllers, antennas, mechanical systems, and physical systems may sometimes be designed using purely analytical methods. However, analytical methods often cannot solve difficult problems of design.
Search techniques offer an alternative way to discover a satisfactory solution to a problem when no analytical method is available.
There are several possible techniques for searching a space of candidate designs for circuits, controllers, antennas, mechanical systems, physical systems, and other complex structures. These search techniques include, but are not limited to, hill climbing, simulated annealing, the genetic algorithm, and genetic programming.
A search operates on a space of possible points (entities). When the search is for a design of a complex structure, each possible design for a circuit, controller, antenna, mechanical system, or physical system is viewed as a point in the search space.
A search through any search space is an iterative process that involves starting with one or more entities (points) from the search space, ascertaining the merit of the entity for solving the problem at hand, creating a new candidate entity by modifying existing entity(ies), ascertaining the merit of the new candidate entity, and using the merit measure to select among entities. The measure or merit is typically called the “fitness measure” when referring to the search technique of genetic programming, the “energy level” when referring to the search technique of simulated annealing, and the “objective function” measure when referring to the search technique of hill climbing. Some of the other additional terms that are commonly used for merit include payoff, score, and profit. For simplicity, the term “fitness” will be used herein to refer to the concept of “merit” used to guide searches. The individual steps of the iterative search process are typically called “generations” when referring to genetic programming, “time-steps” or “cycles” when referring to simulated annealing, and “steps” or “time steps” when referring to hill climbing. However, regardless of the terminology, each of these search techniques proceeds iteratively in discrete stages.
Search techniques do not find solutions by analysis or proof. Instead, they iteratively search a space of candidate points for a solution. The search is guided by the fitness measure. Search techniques typically require large amounts of computation.
Search by Use of Hill Climbing
Simple hill climbing involves starting with a single initial entity (point) in the search space, ascertaining the fitness of the entity, creating a new candidate entity, ascertaining the fitness of the new candidate entity, and using the fitness measure to select between the preexisting entity and the new candidate entity. The new candidate entity is created by a problem-specific modification operation (often a probabilistic operation) that modifies the current entity (point) in the search space in order to obtain a new (usually nearby) candidate entity in the search space. In hill climbing, a new candidate point with a better fitness than the preexisting point is unconditionally selected. Hill climbing is a point-to-point search technique in the sense that the search proceeds from a single point in the search space of the problem to another single point.
Conducting a search using hill climbing through a space of entities in a nontrivial problem very often results in the search becoming trapped at a local optimum point rather than finding the global optimum point of the search space. In hill climbing (and all other search techniques), it may be necessary to make multiple runs in order to find a satisfactory solution (assuming that the problem-specific modification operation is probabilistic so that different runs can potentially produce different outcomes).
Search by Use of Simulated Annealing
Simulated annealing resembles hill climbing in that it is a point-to-point search technique. See, for example, S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization by Simulated Annealing, in Science 220, pages 671-68, 1983. Like hill climbing, simulated annealing employs a problem-specific probabilistic modification operation (typically termed a “mutation” when referring to simulated annealing) for modifying the current entity (point) in the search space in order to obtain a new candidate entity. At each step of the search, the current point in the search space is modified using the modification operator and the new point's fitness is ascertained.
Specifically, simulated annealing involves starting with a single initial entity (point) in the search space, ascertaining the fitness of the entity, creating a new candidate entity, ascertaining the fitness of the new candidate entity, and using the fitness measure to select between the preexisting entity and the new candidate entity. Simulated annealing always selects the new candidate entity if it is better than the preexisting entity. That is, it operates in the same way as hill climbing in such cases.
However, simulated annealing differs from hill climbing in the way it handles the case when the new candidate entity is worse than the preexisting entity. In this case, the Metropolis algorithm and the Boltzmann equation are applied to determine whether to accept a non-improving new candidate entity. A run of simulated annealing is governed by an annealing schedule in which a temperature T changes as the run proceeds (typically in an exponentially monotonically decreasing way). That is, the temperature starts at a high level early in the run and falls as the run progresses. The effect of the Metropolis algorithm and the Boltzmann equation are that the probability of acceptance of a non-improving modification is greater if the fitness difference is small or if the temperature T is high. Thus, fairly large non-improving modifications are likely to be accepted early in the run (when the temperature is high). That is, simulated annealing resembles blind random search in early stages of the run because all improving modifications and most non-improving modifications are accepted. However, later in the run (when the system has cooled), only small non-improving modifications are likely to be accepted. That is, simulated annealing resembles hill climbing in later stages of the run. If a modification is not accepted at any step of the run of simulated annealing, the probabilistic modification operator is re-invoked to produce another new point.
Search by Use of Genetic Programming
“Genetic programming” (also referred to as the “non-linear genetic algorithm” or the “hierarchical genetic algorithm” in previous years) is described in the book entitled Genetic Programming: On the Programming of Computers by Means of Natural Selection, by John R. Koza, Cambridge, Mass.: The MIT Press, 1992; the book entitled Genetic Programming II: Automatic Discovery of Reusable Programs, by John R. Koza, Cambridge, Mass.: The MIT Press, 1994; and in U.S. Pat. Nos. 4,935,877, 5,136,686, 5,148,513, 5,343,554, 5,742,738, and 5,867,397.
Genetic programming is referred to as “non-linear” or “hierarchical” because the original genetic algorithm described by John H. Holland in Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, Ann Arbor, Mich.: University of Michigan Press, Second edition, Cambridge, Mass.: The MIT Press, 1975, operated on linear strings of characters (resembling chromosomes in nature), whereas genetic programming operates on hierarchical program trees of various sizes and shapes.
Genetic programming is capable of evolving computer programs that solve, or approximately solve, a variety of problems from a variety of fields. Genetic programming may start with a “primordial ooze” of randomly generated programs composed of the available programmatic ingredients. It then applies the principles of animal husbandry to breed a new (and often improved) population of programs. Genetic programming may perform the breeding in a domain-independent way using the Darwinian principle of survival of the fittest, an analog of the naturally-occurring genetic operation of crossover (sexual recombination), and occasional mutation. The crossover operation is designed to create syntactically valid offspring programs (given closure amongst the set of ingredients). Genetic programming combines the expressive high-level symbolic representations of computer programs with the near-optimal efficiency of learning associated with the genetic algorithm. A program that solves (or approximately solves) a given problem often emerges from this process.
As demonstrated in the book entitled Genetic Programming II: Automatic Discovery of Reusable Programs, by John R. Koza, Cambridge, Mass.: The MIT Press, 1994, genetic programming can evolve multi-part programs having a main program and one or more reusable, parameterized, hierarchically-called subprograms (called automatically defined functions or ADFs). See U.S. Pat. No. 5,343,554, entitled “A Non-Linear Genetic Process for Data Encoding and for Solving Problems Using Automatically Defined Functions”, issued Aug. 30, 1994, by Koza, John R., and Rice, James P.
The architecture of a multi-part program may consist of a result-producing branch and automatically defined function(s) and involves:                (1) the total number of automatically defined functions,        (2) the number of arguments (if any) possessed by each automatically defined function, and        (3) if there is more than one automatically defined function in a program, the nature of the hierarchical references (including recursive references), if any, allowed among the automatically defined functions.        
There are a variety of ways of determining the architecture for a computer program that is to be evolved using genetic programming, such as                (1) the human user may pre-specify the architecture of the overall program as part of his or her preparatory steps prior to launching the run; and        (2) architecture-altering operations may be used during the run to automatically create the architecture of the program during the run.        
Architecture-altering operations, enable genetic programming to automatically determine the number of subroutines, the number of arguments that each possesses, and the nature of the hierarchical references, if any, among such automatically defined functions. See U.S. Pat. No. 5,742,738, entitled “Simultaneous Evolution of the Architecture of a Multi-part Program to Solve a Problem Using Architecture Altering Operations,” issued Apr. 21, 1998, by Koza, John R., Andre, David, and Tackett, Walter Alden. Certain additional architecture-altering operations also enable genetic programming to automatically determine whether and how to use internal memory, iterations, and recursion in evolved programs.
Genetic programming may breed computer programs to solve problems by executing the following steps:                (1) Generate an initial population of random compositions (i.e., programs) of the functions and terminals of the problem.        (2) Iteratively perform the following substeps (referred to herein as a generation) on the population until the termination criterion has been satisfied:                    (A) Execute each program in the population and assign it a fitness value using the fitness measure.            (B) Create a new population of programs by applying the following operations. The operations are applied to program(s) selected from the population with a probability based on fitness (with reselection allowed).                            (i) Reproduction: Copy the selected program to the new population.                (ii) Crossover: Create a new offspring program for the new population by recombining randomly chosen parts of two selected programs.                (iii) Mutation: Create one new offspring program for the new population by randomly mutating a randomly chosen part of the selected program.                (iv) Architecture-altering operations: Select an architecture-altering operation from the available repertoire of such operations and create one new offspring program for the new population by applying the selected architecture-altering operation to the selected program.                                                (3) Designate the individual program that is identified by result designation (e.g., the best-so-far individual) as the result of the run of genetic programming. This result may be a solution (or an approximate solution) to the problem.        
Genetic programming conducts a search for a solution, or approximate solution, to a problem.
Simulated annealing is similar to genetic programming in that it sometimes accepts a newly created point that is known to be inferior in the hope that it will lead to better points. That is, neither simulated annealing nor genetic programming is a purely greedy search algorithm. Simulated annealing differs from genetic programming in that simulated annealing unconditionally accepts an improving modification while genetic programming does not always do this. Simulated annealing and hill climbing differ from searches conducted by the genetic programming in that simulated annealing and hill climbing are point-to-point search techniques. That is, only one entity (point) is retained at each generation of the search in simulated annealing or hill climbing. There is no population of entities in simulated annealing or hill climbing (as there is in genetic programming). Because there is no population in simulated annealing or hill climbing, there is no analog to the crossover operation of genetic programming (where two parents mate, or recombine, to produce offspring).
Genetic programming is preferable to hill climbing because hill climbing operates on only a single entity (point) in the search space of the problem and because hill climbing greedily unconditionally selects a better point in preference to a worse point. Because of this, hill climbing tends to become trapped on local optimum points that are not global optimum points. Simulated annealing also operates on a single entity (point) in the search space of the problem; however, simulated annealing is preferable to hill climbing because it typically uses the Metropolis algorithm and the Boltzmann equation to avoid becoming entrapped on locally optimum points.
Genetic programming is preferable to simulated annealing (which resembles a genetic algorithm operating on a population of size 1) because the existence of a population greater than one permits crossover (recombination) to occur between two (or more) parents, each chosen probabilistically based on their fitness. Experience indicates that the recombination of parts of already fit parents often yields superior offspring in a far more rapid way than that provided by search techniques that lack recombination.
Genetic programming has been successfully used to solve many difficult problems involving the search of complex spaces. In particular, genetic programming has been successfully applied to the problem of designing complex structures.
For example, genetic programming has been used for automatically creating the topology and sizing for an analog electrical circuit from a high-level statement of the circuit's desired behavior. See U.S. Pat. No. 5,867,397, entitled “Method and Apparatus for Automated Design of Complex Structures Using Genetic Programming,” issued Feb. 2, 1999.
As another example, genetic programming has been used for creating the design for both the topology and tuning of automatic controllers. See Koza, John R., Keane, Martin A., Yu, Jessen, Bennett, Forrest H III, and Mydlowec, William, Automatic Creation of Human-Competitive Programs and Controllers by Means of Genetic Programming, Genetic Programming and Evolvable Machines, (1) 121-164, 2000.
As yet another example, genetic programming has been used to create the design of antennas. See Jones, Eric A., Genetic Design of Antennas and Electronic Circuits. PhD Thesis, Department of Electrical and Computer Engineering, Duke University, 1999.
Moreover, the genetic algorithm operating on fixed-length character strings has also been successfully used to solve many difficult problems involving the search of complex spaces.
In particular, the genetic algorithm has been successfully applied to the problem of designing electrical circuits such a amplifiers (Kruiskamp, Wim and Domine Leenaerts, “DARWIN: CMOS opamp synthesis by means of a genetic algorithm,” Proceedings of the 32nd Design Automation Conference, New York, N.Y.: Association for Computing Machinery, 1995), filters (Grimbleby, J. B., “Automatic analogue network synthesis using genetic algorithms,” Proceedings of the First International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications, London: Institution of Electrical Engineers, 1995), and frequency discriminators (Thompson, Adrian, “Silicon evolution,” in Koza, John R., Goldberg, David E., Fogel, David B., and Riolo, Rick L. (editors), Genetic Programming 1996: Proceedings of the First Annual Conference, Cambridge, Mass.: MIT Press, 1996).
Also, the genetic algorithm has been successfully used to automatically create the design for controllers by many researchers. See, for example, Man, K. F., Tang, K. S., Kwong, S., and Halang, W. A., Genetic Algorithms: Concepts and Designs, London: Springer-Verlag, 1999.
In addition, the genetic algorithm has been successfully used to automatically create the design for antennas. See U.S. Pat. No. 5,719,794, entitled Process for the Design of Antennas using Genetic Algorithm, issued on Feb. 17, 1998, to Altshuler, Edward E. and Linden; Derek S.
Genetic programming, the genetic algorithm, simulated annealing, and other search techniques approach a design problem in terms of “what needs to be done” as opposed to “how to do it.” These search techniques are capable of creating varied designs because they employ a probabilistic process that is not encumbered by the preconceptions that often unconsciously channel human thinking down familiar paths. All of these searches are driven by the fitness measure of the particular design problem at hand.
Although genetic programming, the genetic algorithm, simulated annealing, and other search techniques have each demonstrated an ability to automatically create useful entities (i.e., those that satisfy technical design requirements), previous uses of these techniques have not addressed the issue of actively avoiding the creation of an entity that possesses the key characteristics of preexisting technology. In other words, previous efforts have not focused on an automated design process that produces designs that avoid known prior art.
The design process for electrical circuits may begin with a high-level description of the circuit's desired behavior and include creation of the circuit's topology and sizing. The topology of a circuit typically entails specifying the gross number of components in the circuit, the type (e.g., a capacitor) of each component, and the nodes to which each of a component's leads are to be connected. Sizing typically involves specifying the values (typically numerical) of each of the circuit's components.
Until recently, there has been no general technique for automatically creating the topology and sizing for an analog electrical circuit from a high-level statement of the circuit's desired behavior. In describing the process of creating the topology and sizing of an analog circuit, Aaserud and Nielsen (1995) observed,                Analog designers are few and far between. In contrast to digital design, most of the analog circuits are still handcrafted by the experts or so-called “zahs” of analog design. The design process is characterized by a combination of experience and intuition and requires a thorough knowledge of the process characteristics and the detailed specifications of the actual product.        Analog circuit design is known to be a knowledge-intensive, multiphase, iterative task, which usually stretches over a significant period of time and is performed by designers with a large portfolio of skills. It is therefore considered by many to be a form of art rather than a science.        
There has been extensive previous work on the problem of automating various aspects of the design of electrical circuits using simulated annealing, artificial intelligence, and other techniques.
Recently, a general technique using genetic programming has emerged for automatically creating the topology and sizing for an analog electrical circuit from a high-level statement of the circuit's desired behavior.
Numerous circuits have been designed using genetic programming, including lowpass, highpass, bandpass, bandstop, crossover, multiple bandpass, and asymmetric bandpass filters, amplifiers, computational circuits, a temperature-sensing circuit, a voltage reference circuit, frequency-measuring circuits, and source identification circuits. The circuits evolved using genetic programming include six previously patented circuits and other circuits that were considered achievements at the time when they were first invented.
Genetic programming can be applied to circuit design by establishing a mapping between the rooted, point-labeled trees (i.e., acyclic graphs) with ordered branches used in genetic programming and the specialized type of line-labeled cyclic graphs germane to electrical circuits.
For electrical circuits, an embryo consisting of one (and sometime more) modifiable wires is used as a starting point. The embryo is embedded into a test fixture consisting of fixed (hard-wired) components (such as a source resistor and a load resistor) and certain fixed wires that provide connectivity to the circuit's external inputs and outputs. Until the modifiable wires are modified by the developmental process, the circuit produces only trivial output. An electrical circuit is developed by progressively applying the functions in a circuit-constructing program tree (in the population being bred by genetic programming) to the modifiable wires of the original embryo and, during the developmental process, to newly created modifiable components and modifiable wires.
The functions in the circuit-constructing program trees may be divided into five categories: (1) topology-modifying functions that alter the circuit topology, (2) component-creating functions that insert components into the circuit, (3) development-controlling functions that control the development process by which the embryo and its successors is changed into a fully developed circuit, (4) arithmetic-performing functions that appear in subtrees as argument(s) to the component-creating functions and specify the numerical value of the component, and (5) automatically defined functions that appear in the function-defining branches and potentially enable certain substructures of the circuit to be reused (with parameterization).
Each branch of the program tree may be created in accordance with a constrained syntactic structure. Branches may be composed of construction-continuing subtrees that continue the developmental process and arithmetic-performing subtrees that determine the numerical value of components. Topology-modifying functions have one or more construction-continuing subtrees, but no arithmetic-performing subtree. Component-creating functions have one or more construction-continuing subtrees and typically have one arithmetic-performing subtree. This constrained syntactic structure is preserved using structure-preserving crossover with point typing.
The foregoing methods for automatically creating circuit topology and sizing do not address the problem of automatically creating novel structures that meet design requirements and that do not possess key characteristics of preexisting technology.
Controllers are another category of complex structures that are difficult to design. The purpose of a controller is to solicit an actual response of a system that is to be controlled (conventionally called the plant) to match a desired response (called the reference signal or command signal). Controllers (control systems) are ubiquitous in industry.
As an example of a controller, the driver of a car may set the cruise control device to request that the car run at 60 miles per hour. The reference signal (command signal) is 60 miles per hour. The controller measures the difference between the reference signal (the desired speed) and the car's actual speed (the plant response). The controller then adjusts the fuel so as to flow into the car's engine so as to cause the car to run at the desired speed of 60 miles per hour.
There are many different measures of merit that are commonly applied to controllers. For example, it is common to want to minimize the time required to bring about the desired response of the plant. This is often measured by the integral of the time-weighted absolute error (ITAE).
The measure of merit for a real-world controller typically involves several different (usually conflicting) considerations. That is, the requirements are multiobjective. For example, in addition to wanting to minimize the time required to bring about the desired change in the plant, it is also common to simultaneously want to avoid significantly overshooting the desired values for the plant response. For example, although the occupant of a chilly room may want the controller to bring the temperature of the room to 70 degrees quickly, speed is not the only consideration. In particular, the occupant of the room doesn't want to reach 70 degrees by, say, first raising the temperature to 110 degrees (overshooting the reference signal) and then letting the room cool to the desired 70 degrees. In fact, he would prefer that the temperature rose to 70 degrees reasonably quickly with little or no overshoot above 70 degrees.
Controllers can be composed of a variety of types of signal processing blocks that process signals in the time-domain. Examples of such signal processing blocks include, but are not limited to, gain, lead, lag, integrator, differentiator, adder, inverter, subtractor, delay, and multiplier. Each of these processing blocks has one or more inputs. Each has a single output. The input to a controller typically consists of the reference signal(s) and the plant response(s) or, sometimes, just the difference (error) between each reference signal and the corresponding plant response. The output of a controller consists of control variable(s) that are passed to the plant.
One or more parameter values are required to completely specify many of the signal processing blocks used in controllers. For example, the complete specification of a gain block requires specification of its amplification factor (e.g., 100-to-1 or 40 decibel amplification). The specification of these parameter values (which are typically numerical values) is sometimes called “tuning.”
The individual signal processing blocks of a controller are coupled to one another in a particular topological arrangement. The topology of a controller entails the specification of the total number of processing blocks to be employed in the controller, the type of each block (e.g., gain, lead, lag, integrator, differentiator, adder, inverter, subtractor, and multiplier), and the connections between the input point(s) and the output point of each block in the controller.
The process of creating (e.g., synthesizing) a design of a controller entails making decisions concerning the total number of processing blocks to be employed in the controller, the type of each block (e.g., lead, lag, gain, integrator, differentiator, adder, inverter, subtractor, and multiplier), the interconnections between the blocks (including the existence, if any, of internal feedback between the processing blocks of the controller) and the values of all numerical parameters for the blocks.
Conventional analytical techniques have been successfully applied over the years to the design of PID controllers (i.e., controllers consisting of a proportional, integrative, and derivative signal processing block) and various other specific types of controllers. However, there is been no general analytical technique for automatically creating the topology and tuning for a controller from a high-level statement of the controller's desired behavior and characteristics. In particular, there has been no existing general-purpose analytic method for automatically creating a controller for arbitrary linear and non-linear plants that can simultaneously optimize prespecified combinations of performance metrics (such as reducing, and maybe even minimizing, the time required to bring the plant outputs to the desired values as measured by the integral of the time-weighted absolute error or the integral of the squared error), satisfy time-domain constraints (such as overshoot, disturbance rejection, limits on control variables, and limits on state variables), and satisfy frequency domain constraints (bandwidth).
Recently, however, a general technique using genetic programming has emerged for automatically creating the topology and tuning for a controller from a high-level statement of the controller's desired behavior and characteristics. See Koza, John R., Keane, Martin A., Yu, Jessen, Bennett, Forrest H III, and Mydlowec, William, Automatic Creation of Human-Competitive Programs and Controllers by Means of Genetic Programming, Genetic Programming and Evolvable Machines, (1) 121-164, 2000.
Numerous different controllers have been designed using genetic programming. As in the case of the automatic synthesis of the topology and sizing of analog electrical circuits, the foregoing methods for automatically creating the topology and tuning for controllers did not address the problem of automatically creating controllers that satisfy the basic technical design requirements and that also simultaneously avoid the key characteristics of preexisting technology.
Similarly, the previously cited efforts for the automatic synthesis of antennas did not address the problem of automatically creating antennas that satisfy the basic technical design requirements of the antenna and that simultaneously avoid the key characteristics of preexisting antenna technology.